/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item32;

import org.junit.Test;

import java.util.ArrayList;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:PrintFromTopToBottom.java v1.0 2018/8/6 上午1:27 LvJing Exp $
 */
public class PrintFromTopToBottom {

    /**
     * 面试题32：从上往下打印出二叉树的每个节点，同层节点从左至右打印。
     * 思路：其实就是层次遍历二叉树，只要知道这个就简单了。这种遍历方式需要借助队列，把根节点的左孩子、右孩子推入队列，再从队列中取出左孩子，
     * 做同样的推入其左孩子和右孩子，下次再把队列出队，即获取到根节点的右孩子，一直做这样的操作，知道队列没有元素了。
     */
    public class Solution {
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            ArrayList<Integer> result = new ArrayList<>();
            ArrayList<TreeNode> queue = new ArrayList<>();// 用ArrayList模拟队列，算法题一般限制使用其他工具类

            if (root == null) {
                return result;
            }

            queue.add(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.remove(0);
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);

                System.out.print(node.val);
                System.out.print("|");
                result.add(node.val);
            }
            System.out.println();
            return result;
        }
    }

    public class TreeNode {
        int      val;
        TreeNode left  = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    @Test
    public void test01() {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(8, new TreeNode(6, new TreeNode(5), new TreeNode(7)),
                new TreeNode(10, new TreeNode(9), new TreeNode(11)));

        solution.PrintFromTopToBottom(root);
    }
}
